package com.company.algo.niuke;

/**
 只能进行一次交易，
 解法1：贪心，遍历中同时记录价格的最小值与当前价格进行相减，从而得到最大利润
 解法2：【动态规划，忘了咋定义】
 dp[i][0]表示第i天持有股票所得最多现金
 dp[i][1]表示第i天不持有股票所得最多现金
 dp[i][0] = max(-prices[i],dp[i-1][0])，今天刚买入 or 前一天就持有
 dp[i][1] = max(dp[i-1][0]+prices[i],dp[i-1][1]), 今天刚卖出 or 前一天就卖出
 初始值：dp[0][0]= -prices[0], dp[0][1] = 0
 */
public class StockProblem1 {
    public int maxProfit (int[] prices) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = - prices[0];
        for (int i = 1; i <prices.length ; i++) {
            dp[i][0] = Math.max(dp[i-1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i-1][0]+prices[i],dp[i-1][1]);
        }
        return dp[prices.length-1][1];
    }
}
